<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<meta name="viewport" content="width=device-width,initial-scale=1,minimum-scale=1,maximum-scale=1,user-scalable=no" />
		<script src="./js/jquery.min.js" type="text/javascript" charset="utf-8"></script>
		<title>BP、KMP算法可视化实现-邓永盛</title>
		<style type="text/css">
			.wrapper {
				width: fit-content;
				display: block;
				margin-left: auto;
				margin-right: auto;
			h1 {
				text-align: center;
				background-color: white;
			}

			h1 {
				text-align: center;
			}

			table {
				border: none;
				margin-left: auto;
				margin-right: auto;
			}

			table td {
				border: none;
			}

			table td p {
				text-align: left;
			}

			input {
				font-size: 16px;
			}

			button {
				font-size: 15px;
			}

			.examples {
				font-size: 14px;
			}

			.miss {
				color: royalblue;
				background-color: yellow;
			}

			.matching {
				color: coral;
				background-color: green;
			}

			.current {
				color: white;
				background-color: red;
			}

			font {
				font-family: Consolas;
				padding-left: 3px;
				padding-right: 3px;
			}

			#show {
				font-size: 20px;
			}

			#show p {
				margin: 0px;
			}
		</style>
	</head>
	<body>
		<div class="wrapper" width="300px">
			<h1>字符串匹配BP、KMP算法的JavaScript可视化实现</h1>
			<table>
				<tr>
					<td>主字符串：</td>
					<td><input type="text" name="str" id="str" value="abcdfabcdef" onchange="init();" /></td>
				</tr>
				<tr>
					<td>子串：</td>
					<td><input type="text" name="sub_str" id="sub_str" value="abcdef" onchange="init();" /></td>
				</tr>
			</table>

			<p>每步速度(<span id="speed_val">500</span>ms)：<input type="range" name="speed" id="speed" value="500" min="10" max="5000"
				 oninput="setSpeed()" /></p>
			<table>
				<tr>
					<td><button type="button" onclick="BFMatch()">开始BF匹配</button>
					</td>
					<td>
						<button type="button" onclick="KMPMatch()">开始KMP匹配</button>
					</td>
				</tr>
				<tr>
					<td>
						<button type="button" id="pause" disabled="disabled" onclick="pauseClick()">暂停</button>
					</td>
					<td>
						<button type="button" id="reset" disabled="disabled" onclick="init()">重置</button>
					</td>
				</tr>
			</table>
			<p class="examples">图例：
				<font class="miss">不匹配部分</font>
				<font class="matching">匹配成功部分</font>
				<font class="current">当前指针位置</font>
			</p>
			<table id="show">
				<tr>
					<td>
						<p id="strshow"></p>
					</td>
				</tr>
				<tr>
					<td>
						<p id="substrshow"></p>
					</td>
				</tr>
			</table>
			<h4>
				<p id="result"></p>
			</h4>
		</div>
		<script type="text/javascript">
			// 全局变量声明
			var interval = undefined;
			// 主字符串
			var str = undefined;
			// 字串
			var substr = undefined;
			// 主串指针
			var i = undefined;
			// 字串指针
			var j = undefined;
			// 主串开始匹配后的指针
			var k = undefined;
			// 停顿速度
			var speed = 500;
			// 是否暂停
			var pause = false;
			// 当前进行的是BF算法还是KMP算法
			var task;
			// 统计计算的次数
			var step_count = 0;

			function init() {
				if (interval != undefined) {
					clearInterval(interval);
				}
				interval = undefined;

				i = undefined;
				j = undefined;
				k = undefined;
				pause = false;
				step_count = 0;
				speed = parseInt($('#speed').val());
				$('#speed_val').text(speed)
				$('#pause').text('暂停');
				// 清空输出内容
				$('#result').html('');
				load_str();
			}

			function load_str() {
				$('#strshow').html('');
				$('#substrshow').html('');
				str = document.getElementById('str').value;
				if (str.length > 0) {
					$('#strshow').html('')
					for (let ii = 0; ii < str.length; ii++) {
						$('#strshow').append("<font>" + str[ii] + "</font>");
					}
					$('#strshow font:nth-child(1)').addClass('current');
				}
				substr = document.getElementById('sub_str').value;
				if (substr.length > 0) {
					for (let ii = 0; ii < substr.length; ii++) {
						$('#substrshow').append("<font>" + substr[ii] + "</font>");
					}
				}
				$('#substrshow font:nth-child(1)').addClass('current');
			}
<<<<<<< HEAD
			// 取子串对应的next数组
			function getNext(p) {
				let next = new Array(p.length);
				next[0] = -1;
				let j = 0;
				let k = -1;
				while (j < p.length - 1) {
					if (k == -1 || p[j] == p[k]) {
						next[++j] = ++k;
					} else {
						k = next[k];
					}
				}
				return next;
			}
			// KMP算法
			function KMPMatch() {
				init();
				if (interval == undefined) {
					if (str.length > 0 && substr.length > 0) {
						i = 0;
						j = 0;
						k = i;
						task = 'KMP';
						next = getNext(substr);
						// console.log(next);
						interval = setInterval(KMPInterval, speed);
						$('#pause').attr('disabled', false);
					} else {
						alert("字符串和子串不可为空！");
					}
				}
			}

			function KMPInterval() {
				if (pause) {
					return;
				}
				if (i < str.length && j < substr.length) {
					$('#strshow font').removeClass();
					$('#substrshow font').removeClass();
					console.log(i, j, next);
					// 主串不匹配部分上色
					for (let ii = 0; ii < i; ii++) {
						$('#strshow font:nth-child(' + (ii + 1) + ')').addClass('miss');
					}
					// 主串匹配部分上色
					for (let ii = i - j; ii < i; ii++) {
						$('#strshow font:nth-child(' + (ii + 1) + ')').addClass('matching');
					}
					// 主串当前位置
					$('#strshow font:nth-child(' + (i + 1) + ')').addClass('current');
					// 子串已经匹配位置上色
					for (let ii = 0; ii < j; ii++) {
						$('#substrshow font:nth-child(' + (ii + 1) + ')').addClass('matching');
					}
					// 子串当前位置上色
					$('#substrshow font:nth-child(' + (j + 1) + ')').addClass('current');
					if (j == -1 || str[i] == substr[j]) {
						// 当j为-1时，要移动的是i，当然j也要归0
						i++;
						j++;
					} else {
						// i不需要回溯了
						// i = i - j + 1;
						j = next[j]; // j回到指定位置
					}
					step_count++;
				} else {
					// 停止循环
					clearInterval(interval);
					if (j == substr.length) {
						// 隐藏暂停按钮
						$('#pause').attr('disabled', true);
						// 输出结果
						$('#result').text("共比较" + step_count + "次，找到匹配，匹配位置为：（" + (i - j) + ', ' + i + ')');
					} else {
						$('#result').text("共比较" + step_count + "次，没有找到匹配！");
					}
					task = undefined;
					$('#reset').css('visibility', 'visible');
				}
			}
=======

>>>>>>> 5f627ed0fd6344b51c150c91d067dcc4dedd3afe

			function BFMatch() {
				init();
				if (interval == undefined) {
					if (str.length > 0 && substr.length > 0) {
						i = 0;
						j = 0;
						k = i;
						task = 'BF';
						interval = setInterval(BFInterval, speed);
						$('#pause').attr('disabled', false);
					} else {
						alert("字符串和子串不可为空！");
					}
				}
			}

			function BFInterval() {
				// 判断是否为暂停状态
				if (pause) {
					return;
				}
				if (i < str.length && j < substr.length) {
					$('#strshow font').removeClass();
					$('#substrshow font').removeClass();
					// 主串不匹配部分上色
					for (let ii = 0; ii < i; ii++) {
						$('#strshow font:nth-child(' + (ii + 1) + ')').addClass('miss');
					}
					// 主串匹配部分上色
					for (let ii = i; ii < k; ii++) {
						$('#strshow font:nth-child(' + (ii + 1) + ')').addClass('matching');
					}
					// 主串当前位置
					$('#strshow font:nth-child(' + (k + 1) + ')').addClass('current');
					// 子串已经匹配位置上色
					for (let ii = 0; ii < j; ii++) {
						$('#substrshow font:nth-child(' + (ii + 1) + ')').addClass('matching');
					}
					// 字串当前位置上色
					$('#substrshow font:nth-child(' + (j + 1) + ')').addClass('current');

					if (str[k] == substr[j]) {
						// 当前位置匹配，移动到下一个位置
						k++;
						j++;
					} else {
						// 主串指针回溯
						i++;
						k = i;
						// 子串指针回溯
						j = 0;
					}
					step_count++;
				} else {
					clearInterval(interval);
					if (j == substr.length) {
						// 隐藏暂停按钮
						$('#pause').attr('disabled', true);
						// 输出结果
<<<<<<< HEAD
						$('#result').text("共比较" + step_count + "次，找到匹配，匹配位置为：（" + i + ', ' + k + ')');
=======
						$('#result').text("找到匹配，匹配位置为：（" + i + ', ' + k + ')');
>>>>>>> 5f627ed0fd6344b51c150c91d067dcc4dedd3afe
					} else {
						$('#result').text("共比较" + step_count + "次，没有找到匹配！");
					}
					task = undefined;
					$('#reset').css('visibility', 'visible');
				}
			}
			// 修改速度
			function setSpeed() {
				speed = parseInt($('#speed').val());
				$('#speed_val').text(speed);
				if (interval) {
					clearInterval(interval);
					if (task == 'BF') {
						interval = setInterval(BFInterval, speed);
<<<<<<< HEAD
					} else if (task == "KMP") {
						interval = setInterval(KMPInterval, speed);
=======
>>>>>>> 5f627ed0fd6344b51c150c91d067dcc4dedd3afe
					} else {
						alert('错误');
					}
				}
			}
			// 暂停控制
			function pauseClick() {
				pause = !pause;
				if (pause) {
					$('#pause').text('继续');
				} else {
					$('#pause').text('暂停');
				}
			}
			init();
		</script>
		<div id="footer" class="footer" style="bottom: 0px; width: 100%;position: fixed;z-index: -10;font-family: Consolas;">
			<style type="text/css">
				.footer {
					text-align: center;
				}

				.footer a {
					color: #000000;
					text-decoration: none;
				}
			</style>
			<p><strong>Copyright</strong> © 2021 <strong>邓永盛</strong>. <strong>All rights reserved.</strong></p>
			<p><a href="https://beian.miit.gov.cn/">鄂ICP备2021018056号-1</a></p>
			<p>
				<a href="https://gitee.com/deng-yongsheng"><strong>Git</strong>主页</a>
				<a href="mailto:dys.tj@qq.com?subject=来自gp.dengyongsheng.cn的访客">Email:dys.tj@qq.com</a>
			</p>
			<script type="text/javascript">
				function setPosition() {
					if (window.innerHeight > document.body.clientHeight) {
						document.getElementById('footer').style.position = 'fixed';
					} else {
						document.getElementById('footer').style.position = 'relative';
					}
					// console.log('body Resize:' + document.body.clientHeight);
				}
				document.body.onresize = setPosition;
				window.onresize = setPosition;
				setPosition();
			</script>
		</div>
	</body>
</html>
